package ShortestPath;
import java.util.ArrayList;

import Definitions.GraphClass;
import Definitions.NodeClass;


public class ConnectedComponentsAnalyzerClass {
	
	
/*	public class ConnectedComponentsAtALevelClass 
	{
		boolean komsulukMatrisiAtThisLevel[][];
		boolean toplamKomsulukMatrisiUntilThisLevel[][];
		int level;	//1:Initial level(Birinci derece komsular)//1,2,3...
	}*/
	
	
	//ArrayList<ConnectedComponentsAtALevelClass> ConnectedComponentsAtDegreeLevelsList;
	int shortestPathArray[][];
	int komsulukMatrisi[][];				//1.seviye komsular, Adjacency matrix
	int komsulukMatrisiBeforeLastLevel[][];	//Hesaplanan en son seviye, lastValidLevel seviyesi
	int komsulukMatrisiAtLastLevel[][];
	int toplamKomsulukMatrisiAtLastLevel[][];
	int lastValidLevel;
	
	
	GraphClass localg;
	int localEdgeType;
	int oneDimensionalLength;	//Number of nodes
	
	
	public ConnectedComponentsAnalyzerClass(GraphClass g, int edgeType)
	{	
		localg=g;
		localEdgeType=edgeType;
		oneDimensionalLength = localg.getDataSet().size();
		
		shortestPathArray = new int[oneDimensionalLength][oneDimensionalLength];
		for(int i=0; i<oneDimensionalLength; i++)
			for(int j=0; j<oneDimensionalLength; j++)
				shortestPathArray[i][j]=-1;			
		
		komsulukMatrisi = new int[oneDimensionalLength][oneDimensionalLength];
		
		komsulukMatrisiAtLastLevel = new int[oneDimensionalLength][oneDimensionalLength];
		
		toplamKomsulukMatrisiAtLastLevel = new int[oneDimensionalLength][oneDimensionalLength];		
		
		lastValidLevel = 1;	
	}
	
	public void calculateAllConnectedComponents()
	{
		createAdjacencyMatrix();
		//printLastAdjacencyMatrix();
		//printToplamAdjacencyMatrix(1);
		
		calculatePowerOfAdjacencyMatrix(oneDimensionalLength);
		
		//printLastAdjacencyMatrix();
		//printToplamAdjacencyMatrix(2);
		
		printShortestArrayMatrix();
		
		//printAdjacencyMatrix(3);
		//printToplamAdjacencyMatrix(3);
	}
	
	void calculatePowerOfAdjacencyMatrix(int power)
	{
		long processStartTime = 0;
		
		for(int k=1; k<power; k++)
		{
			//System.out.println("lastValidLevel:"+lastValidLevel+" "+"power"+power);
			processStartTime = System.currentTimeMillis();
			calculateOneStepPowerOfAdjacencyMatrix();			
			System.out.println("Total consumed time:"+(System.currentTimeMillis()-processStartTime)/1000);
			//System.out.println("calculateOneStepPowerOfAdjacencyMatrix:"+k);				
			lastValidLevel = k+1;
			updateShortestPathsArray();
			//printMatrix(shortestPathArray, oneDimensionalLength, oneDimensionalLength, "shortestPathArray:");
			
			if(checkIfItIsTimeStopIterationsOfCalculations(k))
			{
				System.out.println("It is time to stop at:"+k);
				break;
			}
			else
				System.out.println("Still continue at:"+k);
				
		}
		
		System.out.println("lastValidLevel son durumda:"+lastValidLevel);
		//ConnectedComponentsAtDegreeLevelsList.get(power);			
	}
	
	void calculateOneStepPowerOfAdjacencyMatrix()
	{
		int sourceMatrix[][], orgAdjacencyMatrix[][];
		
		sourceMatrix = komsulukMatrisiAtLastLevel;
		orgAdjacencyMatrix = komsulukMatrisi;
		
		int sourceMatrixLength=sourceMatrix.length;
		int orgAdjacencyMatrixLength=orgAdjacencyMatrix.length;
		
		//System.out.println("Now printing the details...");
		
		//printMatrix(sourceMatrix, sourceMatrixLength, sourceMatrixLength, "SourceMatrix:");
		//printMatrix(orgAdjacencyMatrix, sourceMatrixLength, sourceMatrixLength, "orgAdjacencyMatrix:");				
		
		komsulukMatrisiAtLastLevel = multiplyMatrices(sourceMatrix, orgAdjacencyMatrix, sourceMatrixLength, sourceMatrixLength, orgAdjacencyMatrixLength, true);
		toplamKomsulukMatrisiAtLastLevel=addTwoMatrices(toplamKomsulukMatrisiAtLastLevel, komsulukMatrisiAtLastLevel, oneDimensionalLength, oneDimensionalLength);		
		
		//printMatrix(toplamKomsulukMatrisiAtLastLevel, sourceMatrixLength, sourceMatrixLength, "toplamKomsulukMatrisiAtLastLevel:");
		
		//System.out.println("The details are printed...");
	}
		
	int[][] addTwoMatrices(int[][] A, int[][] B, int numberOfRows, int numberOfColumns)
	{
		int[][] resultSumMatrix;
		
		resultSumMatrix = new int[numberOfRows][numberOfColumns];
		
		 for(int i = 0; i < numberOfRows; i++)
		 {
		      for(int j = 0; j < numberOfColumns; j++)
		      {
		    	  resultSumMatrix[i][j]=A[i][j] + B[i][j];		    	  
		      }
		 }
		 
		 return resultSumMatrix; 
	}
	
	int[][] multiplyMatrices(int[][] matrixA, int[][] matrixB, int ARowCount, int SharedRowColumnCount, int BColumnCount, boolean isSymmetric)
	{
		int[][] resultMultipliedMatrix;
		int partialSum;
		
		resultMultipliedMatrix = new int[ARowCount][BColumnCount];
		
		if(isSymmetric)
		{
			for(int i = 0; i < ARowCount; i++)
			{			
				//System.out.println("i:"+i);
				for(int j = 0; j <= i; j++) 
				{
					partialSum = 0;
					
					for(int k = 0; k < SharedRowColumnCount; k++)
					{
						partialSum += matrixA[i][k] * matrixB[k][j];		 
					}
					resultMultipliedMatrix[i][j] = partialSum; 
				} 
			 }
			
			for(int i = 0; i < ARowCount; i++)
			{
				for(int j = i+1; j < SharedRowColumnCount; j++)
				{
					resultMultipliedMatrix[i][j] = resultMultipliedMatrix[j][i]; 					
				}			
			}
		}
		else
		{
			for(int i = 0; i < ARowCount; i++)
			{			
				//System.out.println("i:"+i);
				for(int j = 0; j < SharedRowColumnCount; j++) 
				{
					partialSum = 0;
					
					for(int k = 0; k < SharedRowColumnCount; k++)
					{
						partialSum += matrixA[i][k] * matrixB[k][j];		 
					}
					resultMultipliedMatrix[i][j] = partialSum; 
				} 
			 }		
		}		
		
		return resultMultipliedMatrix;		
	}
	
	
	void createAdjacencyMatrix()
	{
		ArrayList<NodeClass> s;
		
		for(int i=0; i<oneDimensionalLength;i++)
		{
			s=localg.getDataSet().get(i).getEdgeList().get(localEdgeType).getNeigbours();
			for(int j=0; j<s.size();j++)
			{
				int order = s.get(j).getOrder();
				komsulukMatrisi[localg.getDataSet().get(i).getOrder()][order] = 1;				
			}			
		}	
		komsulukMatrisiAtLastLevel  = komsulukMatrisi;
		toplamKomsulukMatrisiAtLastLevel = komsulukMatrisi;
		updateShortestPathsArray();
	}

	
	void printLastAdjacencyMatrix()
	{		
		System.out.println("AdjacencyMatrix("+lastValidLevel+")");
		for(int i=0; i<oneDimensionalLength; i++)
		{
			for(int j=0; j<oneDimensionalLength; j++)
				System.out.print(komsulukMatrisiAtLastLevel[i][j]+" ");

			System.out.println();					
		}		
	}
	
	void printToplamAdjacencyMatrix(int level)
	{
		if(level==0)
		{
			System.out.println("HATA: Levels start from 1.");			
		}			
		else if(level>lastValidLevel)
		{
			System.out.println("HATA: This level does not exist:"+level);			
		}
		else
		{
			System.out.println("ToplamAdjacencyMatrix("+level+")");
			level= level-1;
			for(int i=0; i<oneDimensionalLength; i++)
			{
				for(int j=0; j<oneDimensionalLength; j++)
					System.out.print(toplamKomsulukMatrisiAtLastLevel[i][j]+" ");
				
				System.out.println();					
			}			
		}	
		System.out.println();
	}
	
	void printShortestArrayMatrix()
	{	
		System.out.println("Shortest Path Array:");
		for(int i=0; i<oneDimensionalLength; i++)
		{
			for(int j=0; j<oneDimensionalLength; j++)
				System.out.print(shortestPathArray[i][j]+" ");

			System.out.println();					
		}			
		
		System.out.println();
	}
	
	boolean checkIfItIsTimeStopIterationsOfCalculations(int level)
	{		
		for(int i=0; i<oneDimensionalLength; i++)
			for(int j=0; j<oneDimensionalLength; j++)
				if(toplamKomsulukMatrisiAtLastLevel[i][j]==0)
				{
					if(level <= oneDimensionalLength-1)
						return false;
					else 
						return true;
				}		
		return true;
	}
	
	public int findShortestPathBetween(NodeClass a, NodeClass b)
	{
		int orderOfNodeA, orderOfNodeB;
		orderOfNodeA = a.getOrder();
		orderOfNodeB = b.getOrder();
		
		return shortestPathArray[orderOfNodeA][orderOfNodeB];		
	}

	void updateShortestPathsArray()
	{
		//System.out.println("Updating shortest paths for level:"+lastValidLevel);
		for(int i=0; i<oneDimensionalLength; i++)
			for(int j=0; j<oneDimensionalLength; j++)
				if(komsulukMatrisiAtLastLevel[i][j]!=0 && shortestPathArray[i][j]==-1)
				{
					shortestPathArray[i][j]=lastValidLevel;
					//System.out.println("["+(i+1)+"]["+(j+1)+"]");
				}
	}
}
